package leetcode.editor.cn;

import java.util.*;

//[127]单词接龙
public class WordLadder127{
public static void main(String[] args) {
   Solution solution = new WordLadder127().new Solution();

    String[] strings = {"hot", "dot", "dog", "lot", "log", "cog"};
    ArrayList<String> list = new ArrayList<>();
    for (int i = 0; i < strings.length; i++) {
        list.add(strings[i]);
    }
    int i = solution.ladderLength("hit", "cog", list);
    System.out.println("WordLadder127:main:"+i);

}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (wordList == null || wordList.size()<1 || !wordSet.contains(endWord)){
            return 0;
        }
        //因为是无向图，防止。A<->B 重复加入队列。
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        visited.add(endWord);
        //起点遍历
        Queue<String> beginQue = new LinkedList<>();
        beginQue.add(beginWord);
        //终点开始遍历
        Queue<String> endQue = new LinkedList<>();
        endQue.add(endWord);

        int step = 1;
        while (!beginQue.isEmpty() && !endQue.isEmpty()){
            //从小队列，进行扩散，效率高
            if (endQue.size() > beginQue.size()){
                Queue temp = beginQue;
                beginQue = endQue;
                endQue = temp;
            }
            //当前层大小，一边遍历，一边加入图
            int size = beginQue.size();
            for (int i = 0; i < size; i++) {
                String current = beginQue.poll();
                char[] chars = current.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char originChar = chars[j];
                    //每一位，都进行 a,z
                    for (char k = 'a'; k <= 'z'; k++) {
                        if (k == originChar)//是当前 word 忽略
                            continue;
                        chars[j] = k;
                        String nextWord = String.valueOf(chars);
                        if (wordSet.contains(nextWord)){//左右扩散，正好碰上。在同一层。
                            if (endQue.contains(nextWord))return step+1;

                            if (!visited.contains(nextWord)){
                                beginQue.add(nextWord);
                                visited.add(nextWord);
                            }
                        }
                    }
                    //revers
                    chars[j] = originChar;
                }
            }
            //每层+1
            step++;
        }

        return 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}